#include <stdio.h>
#include <string.h>
//https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/
//字典序最小的美丽字符串
//如果一个字符串满足以下条件，则称其为 美丽字符串 ：
//它由英语小写字母表的前 k 个字母组成。
//它不包含任何长度为 2 或更长的回文子字符串。
//给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。
//请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。
//对于长度相同的两个字符串 a 和 b ，如果字符串 a 在与字符串 b 不同的第一个位置上的字符字典序更大，则字符串 a 的字典序大于字符串 b 。
//例如，"abcd" 的字典序比 "abcc" 更大，因为在不同的第一个位置（第四个字符）上 d 的字典序大于 c 。

char * smallestBeautifulString(char * s, int k){
    int len = strlen(s);
    int i = 0;
    for(i = len - 1; i >= 0; i--)
    {
        int flag = 0;
        for(int j = s[i] + 1; j < 'a' + k; j++)
        {
            if((i >= 1 && j == s[i - 1]) || (i >= 2 && j == s[i - 2]))
            continue;
            flag = 1;
            s[i] = j;
            break;
        }
        if(flag == 1)
        break;
    }

    if(i < 0)
    return "";

    for(i = i + 1; i < len; i++)
    {
        for(int j = 'a'; j < 'a' + k; j++)
        {
            if((i >= 1 && j == s[i - 1]) || (i >= 2 && j == s[i - 2]))
            continue;
            s[i] = j;
            break;
        }
    }

    return s;
}

int main()
{
    char arr[] = "ponp";
    smallestBeautifulString(arr, 16);
    return 0;
}